1. Field of the Invention
The present invention relates generally to electronic state machines and more specifically to handshake protocols for electronic state machines.
2. Prior Art
State machines are functional blocks of logic designed to perform specific functions based on the values of input signals. For example, a microcontroller may contain a bus controller state machine and a cache controller state machine. Based on input signals provided by the microcontroller, the bus controller either stores or fetches data from external memory; the cache controller checks for copies of data requested from external memory and stores copies of data as external memory is changed. Upon beginning a fetch from a cacheable region of external memory, the bus controller requests that the cache controller determine if a copy of the desired data is stored in the on-chip cache memory. The cache controller determines if the copy is present and indicates the finding to the bus controller. In this manner the bus controller and cache controller state machines cooperate through handshaking to perform some of the overall functions of the microcontroller.
FIG. 1a illustrates a common request and acknowledge handshake protocol that allows an initiator state machine to request execution of one of two tasks by a target state machine, and also allows the target state machine to indicate to the initiator state machine the start of execution of the requested task. The initiator requests that the target execute either a first or a second task by driving either the REQ1 or REQ2 signal high, respectively. When the target is ready to accept a request the target determines which request is active and drives the ACK (acknowledge) signal high in the following clock cycle to indicate the start of execution of the requested task.
This prior art request/acknowledge handshake protocol presents two problems illustrated by the first and second REQ/ACK combinations shown in the waveforms of FIG. 1b.
First, there is a minimum delay of two clocks after a first task is requested before the initiator can initiate another event that is gated by the start of execution of the first task by the target. Suppose that the initiator needs to initiate the execution of a second task but cannot do so until the initiator knows that the target has started executing an earlier requested first task, i.e. the first task gates the second task. The earliest that the target can initiate the second task is two clock cycles after requesting execution of the first task by the target. This is the case where the target is ready and waiting to execute the first task. For example, as shown in the first REQ1/ACK combination in the waveforms of FIG. 1b, suppose the initiator drives the REQ1 signal high at the beginning of a first clock cycle. If the target is waiting to execute a request, the target will determine which request to service during the first clock cycle and drive the ACK signal high at the beginning of the next, or second, clock cycle to indicate to the initiator that execution of the request is started. The initiator, which is waiting for an indication that the target has started execution, receives the ACK signal going high during the second clock cycle and initiates the second task at the start of the following, or third, clock cycle, two clock cycles after the original request.
Second, in cases of changing multiple requests there is an ambiguity as to which request is acknowledged by the target when the ACK signal is driven high. Resolving the ambiguity requires extra logic. For example, as shown in the second pair of REQ/ACK events in the waveforms of FIG. 1b, suppose the initiator initially drives the REQ1 signal high to request a first task, but later changes and drives the REQ1 signal low and the REQ2 signal high to indicate a new request of a second task (only one request signal can be high at a time). Also suppose that at the time the change in requests occurs, the target drives the ACK signal high acknowledging a request. Is the target acknowledging the REQ 1 request that was high during the previous cycle or the REQ2 request that is currently high? Since the target must decide which request to service during the cycle before driving the ACK signal high, the request corresponding to REQ1 is being acknowledged in this case. To resolve this ambiguity, the initiator must remember the previous state of all of the request signals to understand which request is being acknowledged by a given ACK signal going high. This is typically accomplished by storing the previous state of all REQ signals (i.e. their state during the previous clock cycle) in latches.
The two clock cycle minimum delay problem imposes a performance penalty on the overall function performed by two handshaking state machines. In the case of microprocessors or computer systems, the performance penalty degrades overall microprocessor and computer system performance. The changing request ambiguity problem requires extra logic for each request signal and becomes significant as the number of request signals between state machines increases.
Therefore, a method and apparatus for streamlined handshaking between state machines is needed.